package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

/**
 * TODO 大佬提供的双指针/滑动窗口/子串问题的模板
 * https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems
 * 虽然短, 可读性为0, LC76_4扩展为可读性好的
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC76_3 implements TwoProblem {

    public String minWindow(String s, String t) {
        int[] xx = new int[128];//小技巧, 字符串问题, 字符串有限, 可以不用map
        for (int i = 0; i < t.length(); i++) {
            xx[t.charAt(i)]++;
        }
        int counter = t.length(), begin = 0, end = 0, minSubLength = Integer.MAX_VALUE, head = 0;
        while (end < s.length()) {
            if (xx[s.charAt(end++)]-- > 0) counter--; //in t
            while (counter == 0) { //valid
                if (end - begin < minSubLength) minSubLength = end - (head = begin);
                if (xx[s.charAt(begin++)]++ == 0) counter++;  //make it invalid
            }
        }
        return minSubLength == Integer.MAX_VALUE ? "" : s.substring(head, head + minSubLength);
    }

    public static void main(String[] args) {
        System.out.println(new LC76_3().minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(new LC76_3().minWindow("AZZZZZAxBxCZZZZZCZ", "ABC"));
        System.out.println(new LC76_3().minWindow("a", "aa"));
        System.out.println(new LC76_3().minWindow("a", "ab"));
        System.out.println(new LC76_3().minWindow("cabwefgewcwaefgcf", "cae"));
    }
}
